package com.darwin.darwinIsometric.utils
{
	import com.darwin.darwinIsometric.core.IsoObject;
	import com.darwin.darwinIsometric.core.isoInterface.ISort;
	
	import flash.geom.Point;
	import flash.utils.Dictionary;
	import flash.utils.getTimer;

	/**
	 * 提供场景物件的排序方法
	 * @author Roland
	 */
	public class IsoSort implements ISort
	{	
		
		/**
		 *	普通排序 
		 */
		public static const FORM_NORMAL:String = "normal";
		
		/**
		 *	索引排序 
		 */
		public static const FORM_DICINDEX:String = "dicIndex";
		
		/**
		 *	基数排序 
		 */
		public static const FORM_RADIX:String = "radix";
		
		/**
		 *	高坐标段位数 
		 */
		private static var _indexAccuracyH:int = 10;
		/**
		 *	中坐标段位数 
		 */
		private static var _indexAccuracyM:int = 1000000;
		/**
		 *	低坐标段位数
		 */
		private static var _indexAccuracyL:int = 1000000;
		/**
		 *	使用的排序方式
		 */
		private var form:String = FORM_NORMAL;
		private var _size:int;
		private var _midDic:Dictionary;

		
		/**
		 * 实例化一个排序类
		 * @param zNum 场景中每个格子的大小
		 */
		public function IsoSort(size:int)
		{
			_size = size;
		}
		
		/**
		 *	对传入场景物件列表进行排序
		 * @param isoList 场景物件列表
		 * @return 
		 * 
		 */
		public function fullSort(isoList:Array):Array
		{
			if(form==IsoSort.FORM_NORMAL)
			{
				isoList.sortOn("sortIndex",Array.NUMERIC);
			}else if(form==IsoSort.FORM_DICINDEX)
			{
				return dicSort(isoList);
			}else if(form == IsoSort.FORM_RADIX){
				return radixSort(isoList);
			}else{
				return isoList.sort(isoSortFn);
			}
			return isoList;
		}
		
		
		/**
		 *	 将insert列表中的物件插入到target列表中并进行排序
		 * <BR><B>当插入数量>=40时将自行切换为全排序</B>
		 * @param target 目标数组 (此数组应当已经为有序状态)
		 * @param insert 需要插入target中的无序数组
		 * @return 经过排序的列表
		 * 
		 */
		public function insertSort(targetList:Array,insertList:Array):Array
		{			
			var i:int = 0;
			if(form == IsoSort.FORM_NORMAL)
			{
				for (i = 0; i < insertList.length; i++) 
				{
					targetList.push(insertList[i]);
				}
				return fullSort(targetList);
			}
			else if(form==IsoSort.FORM_DICINDEX)
			{
				if(insertList.length<=40)
				{
					return dicInsert(targetList,insertList);
				}else{
					for (i = 0; i < insertList.length; i++) 
					{
						targetList.push(insertList[i]);
					}
					return dicSort(targetList);
				}
			}else if(form == IsoSort.FORM_RADIX){
				for (i = 0; i < insertList.length; i++) 
				{
					targetList.push(insertList[i]);
				}
				return radixSort(targetList);
			}else{
				for (i = 0; i < insertList.length; i++) 
				{
					targetList.push(insertList[i]);
				}
				return targetList.sort(isoSortFn);
			}
			
		}
		
		
		/**
		 *	插入式动态索引，插入数量<=40时快于全排序 
		 * @param targetList
		 * @param insertList
		 * @return 
		 * 
		 */
		private function dicInsert(targetList:Array,insertList:Array):Array
		{
			dicSort(insertList);
			var totalLength:int = targetList.length + insertList.length;
			var insertIndex:int = 0;
			for (var i:int = 0; i < totalLength; i++) 
			{
				if(insertIndex<insertList.length)
				{
					if(i<targetList.length)
					{
						var result:Number = isoSortFn(insertList[insertIndex],targetList[i]);
						if(result<0)
						{
							targetList.splice(i,0,insertList[insertIndex]);
							insertIndex++;
						}
					}else{
						targetList.push(insertList[insertIndex]);
						insertIndex++;
					}
				}else{
					break;
				}
			}
			return targetList;
		}
		
		/**
		 *	 动态索引排序
		 */
		private function dicSort(isoList:Array):Array
		{
			var $fullIsoDic:Dictionary = new Dictionary();
			var $maxIndexH:int = int.MIN_VALUE;//高位索引最大值
			var $minIndexH:int = int.MAX_VALUE;//高位索引最小值
			var $indexHList:Vector.<Object> = new Vector.<Object>(21);//高位索引列表，用来保存对应中位索引最大最小值
			var t:Number = getTimer();
			for (var i:int = 0; i < isoList.length; i++) 
			{
				var iso:IsoObject = isoList[i];
				if(iso)
				{
					var mid:Point = getMidPoint(new Point(iso.x3d,iso.z3d),iso.floorWidth,iso.floorHeight);
					var indexH:int = iso.layerIndex;
					var indexM:int = mid.x/_size + mid.y/_size;
					var indexL:int = mid.x/_size;
					var index:Number =indexH*_indexAccuracyM*_indexAccuracyL + indexM*_indexAccuracyL+indexL;
					if($fullIsoDic[index] == null)
					{
						$fullIsoDic[index] = new Array();
					}
					$fullIsoDic[index].push(iso);
					if(indexH<$minIndexH)$minIndexH = indexH;
					if(indexH>$maxIndexH)$maxIndexH = indexH;	
					if($indexHList[indexH]==null){
						$indexHList[indexH] = {"minIndexM":int.MAX_VALUE,"maxIndexM":int.MIN_VALUE};
					}
					if(indexM<$indexHList[indexH]["minIndexM"])$indexHList[indexH]["minIndexM"] = indexM;
					if(indexM>$indexHList[indexH]["maxIndexM"])$indexHList[indexH]["maxIndexM"] = indexM;
					if($indexHList[indexH][indexM]==null){
						$indexHList[indexH][indexM] = {"minIndexL":int.MAX_VALUE,"maxIndexL":int.MIN_VALUE};
					}
					if(indexL<$indexHList[indexH][indexM]["minIndexL"])$indexHList[indexH][indexM]["minIndexL"] = indexL;
					if(indexL>$indexHList[indexH][indexM]["maxIndexL"])$indexHList[indexH][indexM]["maxIndexL"] = indexL;
				}
			}
			trace("动态索引耗时："+(getTimer()-t) + "ms");
			
			var $count:int= 0;
//			t = getTimer();
			for (var IH:int = $minIndexH; IH <= $maxIndexH; IH++) 
			{
				if($indexHList[IH]==null)continue;
				for (var IM:int = $indexHList[IH]["minIndexM"]; IM <= $indexHList[IH]["maxIndexM"]; IM++) 
				{
					if($indexHList[IH][IM]==null)continue;
					for (var IL:int = $indexHList[IH][IM]["minIndexL"]; IL <=  $indexHList[IH][IM]["maxIndexL"]; IL++) 
					{
						var isoVec:Array = $fullIsoDic[IH*_indexAccuracyM*_indexAccuracyL+IM*_indexAccuracyL + IL];
						if(isoVec!=null)
						{
							isoVec.sort(ySortFn);
							for (var k:int = 0; k < isoVec.length; k++) 
							{
								iso = isoVec[k];
								if(iso!=null)
								{
									isoList[$count] = iso;
									$count++;
								}
							}
						}
					}
				}
			}
//			trace("排序耗时："+(getTimer()-t) + "ms");
			return isoList;
		}
		
		/**
		 * 基数排序算法
		 */
		private function radixSort(isoList:Array):Array
		{
			var $maxPsoition:int = 0;//最大的数字位，即数字最大的个数
			var $linkedList:IsoLinkedList = new IsoLinkedList();
			var $currentPosition:int = 0;
			var $arrList:Vector.<IsoLinkedList> = new Vector.<IsoLinkedList>();
			var i:int;
			for(i = 0;i<1000;i++)
			{
				$arrList.push(new IsoLinkedList());
			}
//			var t:int = getTimer();
			for(i = 0;i<isoList.length;i++)
			{
//				var $value:int = isoList[i].middleX + isoList[i].middleZ;
				var $value:int = isoList[i].floorWidth/2 + isoList[i].x3d +  isoList[i].floorHeight/2 + isoList[i].z3d;
				
				var $keyArray:Array = sInt($value);
				if($keyArray.length > $maxPsoition)
				{
					$maxPsoition = $keyArray.length;
				}
				$linkedList.push(new IsoLinkedItem(isoList[i],$keyArray));
			}
//			trace("基数排序",getTimer() - t);
//			t = getTimer();
			while($currentPosition<$maxPsoition)
			{
				while(!$linkedList.isNull())
				{
					var $item:IsoLinkedItem = $linkedList.shift();
					var $cValue:int = $item.keyArray[$currentPosition];
					$arrList[$cValue].push($item);
				}
				$currentPosition++;
				
				for(i = 0;i<1000;i++)
				{
					while(!$arrList[i].isNull())
					{
						$linkedList.push($arrList[i].shift());
					}
				}
			}
			isoList.length = 0;
			while(!$linkedList.isNull())
			{
				isoList.push($linkedList.shift().value);
			}
			
//			trace("基数排序2",getTimer() - t);
			return isoList;
		}
		
		private function sInt(value:int):Array
		{
			var $returnArr:Array = [];
			while(value > 0)
			{
				$returnArr.push(value%1000);
				value = value/1000;
			}
			return $returnArr;
		}
		


		private static function getMidPoint(p:Point,floorWidth:Number,floorHeight:Number):Point
		{
			return new Point(floorWidth/2+p.x,floorHeight/2+p.y);
		}

		private static function midSortFn(aMid:Point,bMid:Point):Number
		{
			var sumA:Number = aMid.x + aMid.y;
			var sumB:Number = bMid.x + bMid.y;
			//中心线判断法
			if(sumA<sumB)
			{
				return -1;
			}else if(sumA>sumB)
			{
				return 1;
			}else{
				return 0;
			}
		}
		
		
		private static function ySortFn(a:IsoObject,b:IsoObject):Number
		{
			if(a.y3d > b.y3d)
			{
				return -1;
			}else if(a.y3d < b.y3d)
			{
				return 1;
			}else{
				return 0;
			}
		}
		
		
		private static function isoSortFn(a:IsoObject,b:IsoObject):Number
		{
			if(a.layerIndex > b.layerIndex)
			{
				return 1;
			}else if(a.layerIndex < b.layerIndex)
			{
				return -1;
			}else{
				if((a.middleX + a.middleZ) > (b.middleX + b.middleZ))
				{
					return 1;
				}else if((a.middleX + a.middleZ) < (b.middleX + b.middleZ)){
					return -1;
				}else{
					return 0;
				}
			}
		}
	}
}